package 面试题16_数值的整数次方.类似斐波那契数列实现.递归实现;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 20:49 2021/2/14
 * @Description：
 */
class Solution {
    public double myPow(double x, int n) {
        // 特殊输入：0的负数次幂
        if (isEqual(x, 0.0)) return 0;

        long b = n;//int32的取值范围为[−2147483648,2147483647]，当n取最左侧值时，取绝对值会越界，因此这里使用long来存储

        long absExponent = Math.abs(b);

        double res = PowerWithUnsignedExponent(x, absExponent);

        if (n < 0) {
            res = 1 / res;
        }

        return res;
    }

    double PowerWithUnsignedExponent(double base, long exponent) {

        if (exponent == 0) {
            return 1;
        }
        if (exponent == 1) {
            return base;
        }

        double result = PowerWithUnsignedExponent(base, exponent >> 1);

        result *= result;

        if ((exponent & 0x1) == 1) {
            result *= base;
        }

        return result;
    }

    boolean isEqual(double num_1, double num_2) {
        double absResult = Math.abs(num_1 - num_2);

        return absResult < 1e-6;
    }

}
